import java.util.ArrayList;
import java.util.List;

/**
 * 01 背包问题
 * 
 * 参考：https://blog.csdn.net/Rex_WUST/article/details/89336939
 * 为什么背包容量足够的情况下，还需要 V(i,j)=max｛V(i-1,j)，V(i-1,j-w(i))+v(i)｝？
 * 
 * V(i-1,j-w(i))+v(i) 表示装了第i个物品后背包中的最大价值，所以当前背包容量 j 中，必定有w(i)个容量给了第i个背包。
因此只剩余j-w(i)个容量用来装，除了第i件物品的其他所有物品。
V(i-1,j-w(i))是前i-1个物品装入容量为j-w(i)的背包中最大价值。
注意，这里有一个问题。前i-1个物品装入容量为j-w(i)的背包中最大价值+物品i的价值。可能不如将，前i-1个物品装入容量为j的背包中得到的价值大。也就是说,可能出现 V(i-1,j) > (V(i-1,j-w(i))+v(i))
比如说，将第i个物品放入背包，可能会导致前面更有价值的物品放不进背包。因此，还不如不把第i个物品放进去，把空间让出来，从而能让前i-1个物品中更有价值的物品能够放入背包。从而让V(i,j)取得最大的值。
所以我们需要 max｛V(i-1,j)，V(i-1,j-w(i))+v(i)｝，来作为把前i个物品装入容量为j的背包中的最优解。
 * 
 */
public class 背包问题01 {

    private static int bagWeight = 8;
    private static List<BagInfo> goodsList = new ArrayList<>();
    
    public static void main(String[] args) {

        goodsList.add(new BagInfo(0, 0));
        goodsList.add(new BagInfo(2, 3));
        goodsList.add(new BagInfo(3, 4));
        goodsList.add(new BagInfo(4, 5));
        goodsList.add(new BagInfo(5, 6));

        int[][] dp = new int[goodsList.size()][bagWeight+1];

        for(int i=0; i<goodsList.size(); i++){
            for(int j=0; j<bagWeight+1; j++){

                if(i == 0){
                    dp[i][j] = goodsList.get(0).weight;
                } else if(j == 0){
                    dp[i][j] = goodsList.get(0).weight;
                } else{

                    if(j<goodsList.get(i).weight){

                        dp[i][j] = dp[i-1][j];
                    } else {
    
                        dp[i][j] = Math.max(dp[i-1][j], dp[i-1][j - goodsList.get(i).weight]+goodsList.get(i).value);
    
                    }

                }

            }
        }

        System.out.println(dp[goodsList.size()-1][bagWeight]);

    }

    private static class BagInfo{

        public int weight;
        public int value;

        public BagInfo(int weight, int value){

            this.weight = weight;
            this.value = value;
        }
    }
}
